package com.sali.排序.raw;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: sali
 * @date: 2025/9/14 下午11:26.
 * @version: 1.0
 */
public class raw7_桶排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 2, 3, 1};
        System.out.println(Arrays.toString(myGetRes(arr)));
    }

    private static int[] myGetRes(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for ( int num : arr ) {
            min = Math.min(num, min);
            max = Math.max(num, max);
        }
        int bucketCount = ( max - min ) / 5 + 1;
        int offset = -min;

        List[] buckets = new List[bucketCount];
        for ( int i = 0; i < bucketCount; i++ ) {
            buckets[i] = new ArrayList<>();
        }

        for ( int num : arr ) {
            buckets[(num + offset) / 5].add(num);
        }
        for ( List<Integer> bucket : buckets ) {
            mySort(bucket);
        }
        int index = 0;
        for (List<Integer> curBucket : buckets) {
            for (Integer num : curBucket) {
                arr[index++] = num;
            }
        }
        return arr;
    }

    private static void mySort(List<Integer> bucket) {
        int sortIndex = 0;
        while ( sortIndex < bucket.size() ) {
            for ( int i = sortIndex; i > 0; i-- ) {
                if ( bucket.get(i) < bucket.get(i-1) ) {
                    int temp = bucket.get(i);
                    bucket.set(i, bucket.get(i-1));
                    bucket.set(i-1, temp);
                } else {
                    break;
                }
            }
            sortIndex++;
        }
    }

}
